# 有序链表转换二叉搜索树

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def buildListNode(nums):
    if len(nums) == 0:
        return None
    head = ListNode(nums[0])
    tmp = head
    for i in range(1, len(nums)):
        tmp.next = ListNode(nums[i])
        tmp = tmp.next
    return head


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if head is None:
            return None
        if head.next is None:
            return TreeNode(head.val)
        slow_pre = head
        slow = head
        fast = head
        while fast is not None:
            if fast.next is not None:
                fast = fast.next.next
            else:
                break
            slow_pre = slow
            slow = slow.next
        root = TreeNode(slow.val)
        slow_pre.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

if __name__ == '__main__':
    so = Solution()
    nums = [-10, -3, 0, 5, 9]
    head = buildListNode(nums)
    r = so.sortedListToBST(head)
    print(r)
